package basic.sort.tree;

import basic.sort.utils.NodeUtil;

/**
 * @author distantstar
 * @version 1.0
 * @date 2021
 * @description basic.sort.tree
 * @since JDK1.8
 *
 * 两个节点的最小公共祖先
 */
public class LowestAncestor {

    /**
     *
     * @param head 树的头结点
     * @param o1 判断节点
     * @param o2 判断节点
     * @return 返回最小公共祖先
     */
    private static NodeUtil lowestAncestor2(NodeUtil head, NodeUtil o1, NodeUtil o2) {
        if (head == null || head == o1 || head == o2) {
            return head;
        }

        NodeUtil left = lowestAncestor2(head.left, o1, o2);
        NodeUtil right = lowestAncestor2(head.right, o1, o2);

        if (left != null && right != null) {
            return head;
        }

        return left != null ? left : right;
    }
}
